#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
using namespace std;

//#define a 10
void foo();
//int main()
//{
//	printf("%d..", a);
//	foo();
//	printf("%d", a);
//	return 0;
//} 
//void foo() {
//#undef a
//#define a 50
//}
//#define Mul(x,y) ++x*++y
//int main()
//{
//	__LINE__;
//		__LINE__;
//	int a = 1;
//	int b = 2;
//	int c = 3;
//	printf("%d..", Mul(a + b, b + c));
//	return 0;
//}
//int main()
//{
//
//	return 0;
//}
//int pall(int k)
//{
//    if (k == 1)
//    {
//        return 1;
//    }
//    if (k == 2)
//    {
//        return 2;
//    }
//    return (2 * pall(k - 1)) + pall(k - 2);
//}
long long pall(int k)
{
    if (k == 1)
    {
        return 1;
    }
    if (k == 2)
    {
        return 2;
    }
    long long a1 = 1;
    long long a2 = 2;
    long long an = 0;
    for (int i = 3; i <= k; i++)
    {
        an = 2 * a2 + a1;
        a1 = a2;
        a2 = an;
    }
    return an;
}

//int main() {
//    long n;
//    long arr[1000000] = { 1,2 };
//    for (int i = 2; i < 1000000; i++)
//    {
//        arr[i] = (arr[i - 1] * 2 + arr[i - 2]) % 32767;
//    }
//    cin >> n;
//    for (int a = 0; a < n; a++)
//    {
//        int b;
//        cin >> b;
//        cout << arr[b - 1] << endl;;
//    }
//}
#include <iostream>
using namespace std;

//int main() {
//    string str;
//    getline(cin, str);
//    int max = str[0];
//    int min = str[0];
//    for (int i = 1; i < str.length(); i++)
//    {
//        if (str[i] > max)
//        {
//            max = str[i];
//        }
//        if (str[i] < min)
//        {
//            min = str[i];
//        }
//    }
//    int count = max - min;
//    int* arr = new int[count + 1];
//    for (int n = 0; n < str.length(); n++)
//    {
//        arr[str[n] - min]++;
//    }
//    int kong = 0;
//    int st = 0;
//    int number = 0;
//    int qt = 0;
//    for (int a = 0; a < count; a++)
//    {
//        if ((arr[a] + min) == 32)
//        {
//            kong++;
//        }
//        if ((arr[a] + min) >= 48 && ((arr[a] + min) <= 57))
//        {
//            number++;
//        }
//        if ((arr[a] + min) >= 97 && ((arr[a] + min) <= 122))
//        {
//            st++;
//        }
//    }
//    cout << st << endl;
//    cout << kong << endl;
//    cout << number << endl;
//    cout << qt << endl;
//}
//int main()
//{
//    cout << pall(878);
//	return 0;
//}